package se.kth.fericss.tree;

/**
 * 
 * @author Fredric
 * A Tree storage system.
 * @param <T>
 */
public class Tree<T extends Comparable<T>>{
	private TreeElement<T> root;
	private int size;
	
	public Tree(){
		size=0;
		root=null;
	}
	/**
	 * 
	 * @author Fredric
	 * A private class to handle the elements stored in the Tree
	 * @param <T>
	 */
	private static class TreeElement<T> {
        public T data;
        public TreeElement<T> left;
        public TreeElement<T> right;
        
        public TreeElement(T data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
	/**
	 * Returns a string representation of all the elements in the tree
	 * Uses a recursive method
	 * @return a string representation of the tree
	 */
	public String toString(){
		String ret = helpString(root);
		return "["+ret.substring(2, ret.length()-2)+"]";
	}
	/**
	 * Help method for the toString() Method
	 * @param next The next element to get the string representation from
	 * @return The string representation of the data in left and right
	 */
	private String helpString(TreeElement<T> next){
		return next!=null?	helpString(next.left)+
							next.data+
							helpString(next.right)
							:", ";
	}
	/**
	 * Finds all the leaves in the tree and returns the number
	 * Uses a recursive method
	 * @return if it's a leaf or else, the leaves of it's children's
	 */
	public int getLeaves(){
		return leaves(root);
	}
	/**
	 * Help method for the getLeaves()
	 * @param next
	 * @return 1 if it's a leaf, otherwise the sum of the child leaves
	 */
	private int leaves(TreeElement<T> next){
		return next==null? 
				0: 
				next.left==null&next.right==null? 
				1: 
				leaves(next.left)+leaves(next.right) ;
	}
	/**
	 * Searches for the element in the tree and returns
	 * True if found else it returns false
	 * It uses a iterative method.
	 * @param t The element to search for
	 * @return True if elements is found, else false
	 */
	public boolean contains(T t){
		if(t==null){
			return false;
		}
		TreeElement<T> next = root;
		while(next!=null){
			if(next.data.compareTo(t) == 0){
				return true;
			}
			else if(next.data.compareTo(t) < 0){
				next = next.right;
			}
			else if(next.data.compareTo(t) > 0){
				next = next.left;
			}
		}
		return false;
	}
	/**
	 * Gets the maximum depth of the tree
	 * Uses a recursive method
	 * @return The tree's maximum depth
	 */
	public int getDepth(){
		return depth(root);
	}
	/**
	 * Help method for the getDepth()
	 * @param next next input to compare depth between the right and left
	 * @return the one with the highest depth of left and right
	 */
	private int depth(TreeElement<T> next){
		if(next==null){
			return 0;
		}
		int leftRoot=1+depth(next.left);
		int rightRoot=1+depth(next.right);
		return leftRoot>rightRoot? leftRoot : rightRoot;
	}

	/**
	 * Inserts new elements into the tree
	 * It uses a iterative method.
	 * Returns true if the element was successfully inserted, otherwise it 
	 * will return false if the element already is present in the tree
	 * @param t The element to be inserted into the tree.
	 * @return False if the element already exists
	 */
	public boolean add(T t){
		TreeElement<T> temp = new TreeElement<T>(t);
		if(t==null){
			return false;
		}
		if(root==null){
			root=temp;
			size++;
			return true;
		}
		TreeElement<T> next = root;
		while(next!=null){
			if(next.data.compareTo(t) == 0){
				return false;
			}
			else if(next.data.compareTo(t) < 0){
				if(next.right==null){
					next.right=temp;
					size++;
					return true;
				}
				else
					next = next.right;
			}
			else if(next.data.compareTo(t) > 0){
				if(next.left==null){
					next.left=temp;
					size++;
					return true;
				}
				else
					next = next.left;
					
			}
		}
		return false;
	}
	/**
	 * Returns the size of the tree.
	 * @return The number of elements in the tree
	 */
	public int getSize(){
		return size;
	}
}
